<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <meta http-equiv="X-UA-Compatible" content="ie=edge" />
    <title>排序算法示例</title>
  </head>
  <body>
    初始数组：
    <div id="init-arr"></div>
    排序后：
    <div id="sorted-arr"></div>
    时间复杂度：
    <div id="o-time"></div>
    空间复杂度：
    <div id="o-space"></div>
    <script>
      var quickSort = function(arr) {
        var len = arr.length;
        if (len < 1) {
          return arr;
        }
        var middleIndex = Math.floor(len / 2);
        var middle = arr.splice(middleIndex, 1)[0];
        var left = [];
        var right = [];

        for (var i = 0; i < len; i++) {
          if (arr[i] < middle) {
            left.push(arr[i]);
          } else {
            right.push(arr[i]);
          }
        }
        return quickSort(left).concat([middle], quickSort(right));
      };

      var arr = [2324, 4, 21, 675, 21, -54];
      var len = arr.length;
      document.getElementById("init-arr").innerHTML = arr.join(",");
      var result = quickSort(arr);
      document.getElementById("sorted-arr").innerHTML = result.join(",");
      document.getElementById("o-time").innerHTML =
        "O(nlogn) " + len * Math.log(len);
      document.getElementById("o-space").innerHTML =
        "O(nlogn) " + len * Math.log(len);
    </script>
  </body>
</html>
